package q128;

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

/**
 * 最长连续序列 内存超出限制[0,1,2,4,8,5,6,7,9,3,55,88,77,99,999999999]
 */
public class Solution128 {
    public int longestConsecutive(int[] nums) {
        // 边界判断
        if (nums.length == 0) return 0;
        int min = Arrays.stream(nums).min().getAsInt();
        int max = Arrays.stream(nums).max().getAsInt();
        if (min == max) return 1;

        // +2 可以让最后一位保持false，以便结束for循环
        boolean[] hold = new boolean[max - min + 2];

        // 偏移量
        int offset = min ;

        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            int p = val - offset; // 数组中的位置
            hold[p] = true;
        }

        // 连续的最大长度
        int maxLen = 0;

        int currentLen = 0; // 当前长度
        for (int i = 0; i < hold.length; i++) {
            if (hold[i]) {
                currentLen += 1;
            } else {
                if (maxLen < currentLen) {
                    maxLen = currentLen;
                }

                currentLen = 0; // 复位
            }
        }

        return maxLen;
    }

    /**
     * 解决超出内存问题
     * @param nums
     * @return
     */
    public int longestConsecutive2(int[] nums) {
        // 边界判断
        if (nums.length == 0) return 0;
        int min = Arrays.stream(nums).min().getAsInt();
        int max = Arrays.stream(nums).max().getAsInt();
        if (min == max) return 1;

        // 每1000分一段
        int segmentSize = 1000;

        Map<Integer, boolean[]> map = new TreeMap<>();

        for (int i = 0; i < nums.length; i++) {
            int key = nums[i] >= 0 ? nums[i] / segmentSize : nums[i] % segmentSize == 0 ? nums[i] / segmentSize : nums[i] / segmentSize - 1;
            int val =  nums[i] >= 0 ? nums[i] % segmentSize : nums[i] % segmentSize == 0 ? 0 : segmentSize + (nums[i] % segmentSize);

            if (map.containsKey(key)) {
                boolean[] booleans = map.get(key);
                booleans[val] = true;
            } else {
                boolean[] hold = new boolean[segmentSize];
                hold[val] = true;
                map.put(key, hold);
            }
        }



        int preLen = 0;
        // 连续的最大长度
        int maxLen = 0;
        for (int key : map.keySet()) {
            boolean[] booleans = map.get(key);

            int currentLen = preLen; // 当前长度
            for (int i = 0; i < booleans.length; i++) {
                if (booleans[i]) {
                    currentLen += 1;
                } else {
                    currentLen = 0; // 复位
                }

                if (i == booleans.length - 1) {
                    if (map.containsKey(key + 1)) {
                        preLen = currentLen;
                    } else {
                        preLen = 0;
                    }
                }

                if (maxLen < currentLen) {
                    maxLen = currentLen;
                }
            }

        }

        return maxLen;
    }

    /**
     * 官方解法
     * @param nums
     * @return
     */
    public int longestConsecutive3(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            set.add(n);
        }

        int maxLen = 0;

        for (Integer num : set) {
            if (!set.contains(num - 1)) {
                int currentLen = 1;

                while (set.contains(num + 1)) {
                    num += 1;
                    currentLen += 1;
                }

                maxLen = Math.max(currentLen, maxLen);
            }
        }
        return maxLen;
    }

    public static void main(String[] args) throws IOException {


//       int[] nums = {0,3,7,2,5,8,4,6,0,1};
//       int[] nums = {1,-1};
//       int[] nums = {1,0,-1, 10, -9, -10};
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(Solution128.class.getClassLoader().getResourceAsStream("q128\\Solution128.txt")));
        String line = bufferedReader.readLine();
        List<Integer> list = Arrays.stream(line.split(",")).map(Integer::parseInt).collect(Collectors.toList());
        int[] nums = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            nums[i] = list.get(i);
        }

        Solution128 solution128 = new Solution128();
        int i = solution128.longestConsecutive3(nums);
        System.out.println(i);

    }
}
